package algorithms.sort;

import static algorithms.Util.binarySearch;
import static algorithms.Util.generateArray;
import static algorithms.Util.getArrayCopy;
import static algorithms.Util.print;
import static algorithms.Util.*;

import org.junit.Assert;
import org.junit.Test;

import algorithms.BaseTest;
import algorithms.tree.BinarySearchTreeSort;

public class SortTest extends BaseTest {
	Integer[] defaultArray = generateArray(10000);
	private static final int PRINT_SIZE = 51;

	private Integer[] sortExecute(ISort<Integer> sorter, Integer[] array) {
		print(array, PRINT_SIZE);
		System.out.println("sortClass:" + sorter.getClass());
		array = sorter.sortwithTimeCounter(array);
		print(array, PRINT_SIZE);
		return array;
	}

	@Test
	public void testBubbleSort() {
		BubbleSort<Integer> sorter = new BubbleSort<>();
		sortExecute(sorter, defaultArray);
	}

	@Test
	public void testSelectionSort() {
		SelectSort<Integer> sorter = new SelectSort<>();
		sortExecute(sorter, defaultArray);
	}

	@Test
	public void testInsertSort() {
		sortExecute(new InsertSort<>(), defaultArray);
	}

	@Test
	public void testCompareShellAndInsert() {
		Integer[] a = generateArray(50000);
		Integer[] ac = getArrayCopy(a);
		sortExecute(new InsertSort<>(), a);
		sortExecute(new ShellSort<>(), ac);
	}

	@Test
	public void testMove() {
		Integer[] a = { 5, 4, 3, 2, 1, 6, 7, 8, 9 };
		for (int i = 1; i < a.length; i++) {
			// 如果待插入元素大于或等于有序序列的最大元素，则不作为
			if (a[i] < a[i - 1]) {
				int tmp = a[i];
				// 从后往前对比
				int k;
				for (k = i - 1; k >= 0 && a[k] > tmp; k--) {
					a[k + 1] = a[k];
				}
				a[k + 1] = tmp;
			}
		}
		print(a);
	}

	@Test
	public void testQuickSort() {
		sortExecute(new QuickSort<>(), generateArray(50000));

	}

	@Test
	public void testBianrySearch() {
		Integer[] a = generateArray(1000);
		sortExecute(new QuickSort<>(), a);
		System.out.println(binarySearch(a, 999, 0, 999));
		// { 1, 12, 23, 44, 65, 76, 77, 88, 92, 98 };
		// Assert.assertEquals(binarySearch(a, 25, 0, 9), 3);
		// Assert.assertEquals(binarySearch(a, 35, 0, 9), 3);
		// Assert.assertEquals(binarySearch(a, 45, 0, 9), 4);
		// Assert.assertEquals(binarySearch(a, 55, 0, 9), 4);
		// Assert.assertEquals(binarySearch(a, 65, 0, 9), 4);
		// Assert.assertEquals(binarySearch(a, 75, 0, 9), 5);
		// Assert.assertEquals(binarySearch(a, 12, 0, 9), 1);
		// Assert.assertEquals(binarySearch(a, 23, 0, 9), 2);
		// Assert.assertEquals(binarySearch(a, 44, 0, 9), 3);
		// Assert.assertEquals(binarySearch(a, 65, 0, 9), 4);
		// Assert.assertEquals(binarySearch(a, 76, 0, 9), 5);
		// Assert.assertEquals(binarySearch(a, 77, 0, 9), 6);
		// Assert.assertEquals(binarySearch(a, 88, 0, 9), 7);
		// Assert.assertEquals(binarySearch(a, 92, 0, 9), 8);
		// Assert.assertEquals(binarySearch(a, 98, 0, 9), 9);
	}

	public <T extends Comparable<T>> void merge(T[] left, int lstart, int lend, T[] right, int rstart, int rend,
			T[] result) {
		int leftLen = left.length, rightLen = right.length;
		int i = 0, j = 0, k = 0;
		while (i < leftLen && j < rightLen) {
			if (left[i].compareTo(right[j]) < 0) {
				result[k++] = left[i++];
			} else {
				result[k++] = right[j++];
			}
		}
		if (i == leftLen) {
			while (j < rightLen) {
				result[k++] = right[j++];
			}
		}
		if (j == rightLen) {
			while (i < leftLen) {
				result[k++] = left[i++];
			}
		}
	}

	@Test
	public void testMerge() {
		Integer[] a = { 1 }, b = { 2, 5, 7, 10, 19 };
		Integer[] c = new Integer[a.length + b.length];
		merge(a, 0, a.length - 1, b, 0, b.length - 1, c);
		print(c);
	}

	public void merge_sort(Integer[] a, int start, int end, Integer[] tmp) {
		if (start < end) {
			int mid = (start + end) / 2;
			merge_sort(a, start, mid, tmp);
			merge_sort(a, mid + 1, end, tmp);
			mergeArray(a, start, mid, end, tmp);
		}
	}

	private void mergeArray(Integer[] a, int start, int mid, int end, Integer[] tmp) {
		int i = start, j = mid + 1, k = start;
		while (i <= mid && j <= end) {
			if (a[i] < a[j]) {
				tmp[k++] = a[i++];
			} else {
				tmp[k++] = a[j++];
			}
		}
		while (i <= mid) {
			tmp[k++] = a[i++];
		}
		while (j <= end) {
			tmp[k++] = a[j++];
		}
		// 反映排序后结果到原数组
		for (int n = start; n <= end; n++) {
			a[n] = tmp[n];
		}

	}

	@Test
	public void testMergeSort() {
		Integer[] a = generateArray(100000);// , 32, 15, 27, 10,
		// merge_sort(a, 0, a.length - 1, tmp);
		sortExecute(new MergeSort<Integer>(), a);
		System.out.println(isArrayMonotoneIncreasing(a));
	}

	@Test
	public void compareSort() {
		Integer[] a = generateArray(1000000);
		Integer[] a_MergeSort = getArrayCopy(a);
		Integer[] a_quicksort = getArrayCopy(a);
		Integer[] a_shellsort = getArrayCopy(a);
		Integer[] a_selectsort = getArrayCopy(a);
		Integer[] a_insertsort = getArrayCopy(a);
		Integer[] a_bubblesort = getArrayCopy(a);
		Integer[] a_tree = getArrayCopy(a);
		a_MergeSort = sortExecute(new MergeSort<Integer>(), a_MergeSort);
		org.junit.Assert.assertTrue(isArrayMonotoneIncreasing(a_MergeSort));

		a_quicksort = sortExecute(new QuickSort<>(), a_quicksort);
		org.junit.Assert.assertTrue(isArrayMonotoneIncreasing(a_quicksort));

		a_shellsort = sortExecute(new ShellSort<>(), a_shellsort);
		org.junit.Assert.assertTrue(isArrayMonotoneIncreasing(a_shellsort));
		// 太慢注释
		// sortExecute(new SelectSort<>(), a_selectsort);
		// org.junit.Assert.assertTrue(isArrayMonotoneIncreasing(a_selectsort));
		//
		// sortExecute(new InsertSort<>(), a_insertsort);
		// org.junit.Assert.assertTrue(isArrayMonotoneIncreasing(a_insertsort));
		//
		// sortExecute(new BubbleSort<>(), a_bubblesort);
		// org.junit.Assert.assertTrue(isArrayMonotoneIncreasing(a_bubblesort));

		a_tree = sortExecute(new BinarySearchTreeSort<>(), a_tree);
		Assert.assertTrue(isArrayMonotoneIncreasing(a_tree));
	}
}
